<html>
<head><meta charset="utf-8"><title>Architecture quetion: to remember or to compute · t-compiler/rust-analyzer · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/index.html">t-compiler/rust-analyzer</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html">Architecture quetion: to remember or to compute</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="183058377"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183058377" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183058377">(Dec 10 2019 at 13:23)</a>:</h4>
<p>This a thread to discuss a problem which I know exists, but which I don't know how to solve.</p>
<p>Consider this sceenshot:</p>
<p><a href="/user_uploads/4715/cglb7pthfqaRgiZmzonus8uZ/pasted_image.png" target="_blank" title="pasted_image.png">pasted image</a> </p>
<div class="message_inline_image"><a href="/user_uploads/4715/cglb7pthfqaRgiZmzonus8uZ/pasted_image.png" target="_blank" title="pasted image"><img src="/user_uploads/4715/cglb7pthfqaRgiZmzonus8uZ/pasted_image.png"></a></div><p>As you see, the <code>::Hash</code> is not syntax highlighted properly, because IDE can't figure out that it is an associated type of the <code>BlockT</code> trait. The architectural problem here is that <code>hir</code> actually knows this correctly! We lose this info on the way from <code>hir</code> to <code>ide</code>, and I'd like to discuss this (pretty general I think problem)</p>



<a name="183058923"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183058923" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183058923">(Dec 10 2019 at 13:31)</a>:</h4>
<p>Specifically, there's a code in <code>hir</code> which lowers <code>Result&lt;Vec&lt;Block::Hash&gt;&gt;</code> syntax to a type (<code>Ty::from_hir</code> (the name is bad)). <em>Inside</em> that method, we properly resolve  <code>::Hash</code>, but we then forget this bit of info: the rest of the compiler is interested only in the results of lowering as a whole, and in the subresult for <code>::Hash</code>.</p>



<a name="183059130"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183059130" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183059130">(Dec 10 2019 at 13:34)</a>:</h4>
<p>So, when in IDE we want to compute gotodef for <code>::Hash</code>, we have two choices:</p>
<ul>
<li>re-derive this info</li>
<li>lookup this info in some table</li>
</ul>
<p>In the first approach, you synthesize a path like <code>Block::Hash</code>, and ask <code>hir</code>: "what would be the result of resolving this path, if it were used in this context", where "this context" is a somewhat fussy concept.</p>
<p>In the second approach, the <code>Ty::from_hir</code> would compute not only the final <code>Ty</code> value, but also an auxilary mapping, <code>&lt;PathSyntax, PathResolution&gt;</code>. This mapping won't be used by the rest of the compiler, but would be used by an IDE for goto def.</p>



<a name="183059359"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183059359" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183059359">(Dec 10 2019 at 13:37)</a>:</h4>
<p>The current approach is obviously a broken mixture of both.</p>
<p>Specifically, we use "re-derive" for "top-level" paths. For paths inside expressions though, we use a side-table approach, because computing the correct lexical scope is tricky. In particular, in the above screenshot we hit the "re-derive" path, and fail, because we don't take into account the scope with generic parameters (which is a pretty complex beast, with assoc types and projections)</p>



<a name="183059604"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183059604" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183059604">(Dec 10 2019 at 13:40)</a>:</h4>
<p>In general, I am starting to believe that trying to re-derive things is a bad idea: that's a hidden copy-paste of code, which is bound to diverge over time, <em>especially</em> in various corner cases.</p>



<a name="183059623"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183059623" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Daniel Mcnab <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183059623">(Dec 10 2019 at 13:40)</a>:</h4>
<p>What type is <code>Result&lt;Vec&lt;Block::Hash&gt;&gt;</code> lowered to, and would this be any different if it was just <code>Block::Hash</code>?</p>



<a name="183059779"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183059779" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Daniel Mcnab <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183059779">(Dec 10 2019 at 13:42)</a>:</h4>
<p>I'm not even certain that those questions make sense, but if they do I hope they can clarify the issue.</p>



<a name="183059841"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183059841" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183059841">(Dec 10 2019 at 13:43)</a>:</h4>
<blockquote>
<p>In general, I am starting to believe that trying to re-derive things is a bad idea: that's a hidden copy-paste of code, which is bound to diverge over time, <em>especially</em> in various corner cases.</p>
</blockquote>
<p>yeah, macro expansion was another example until recently -- the <code>SourceAnalyzer</code> resolved macros again, with sometimes slightly different results</p>



<a name="183059877"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183059877" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183059877">(Dec 10 2019 at 13:43)</a>:</h4>
<p>I would say that it is lower<code>Result&lt;Vec&lt;Block::Hash&gt;&gt;</code>, but with IDs instead of identifiers, and where <code>Block::Hash</code> remebers from which trait the <code>::Hash</code> bit comes. The question makes sense, but the answer is funny "it's the same after lowering, although the meaning is completley different"</p>



<a name="183060012"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183060012" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183060012">(Dec 10 2019 at 13:45)</a>:</h4>
<p>I agree that long-term, anything that's not trivial to derive (i.e. just calling a query) should be remembered</p>



<a name="183060164"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183060164" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183060164">(Dec 10 2019 at 13:46)</a>:</h4>
<p>this is actually kind of similar to the diagnostics problem, isn't it, in that it's some additional 'side channel' information we'd like to produce</p>



<a name="183060882"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183060882" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183060882">(Dec 10 2019 at 13:54)</a>:</h4>
<p>So, let me finish the above write up...</p>
<p>The are several problem with "sidetable" approach as well, I think.</p>
<ul>
<li>it might be tricky to figure out which query you should execute to get the required side-table. In this case, this is probably "what is the type of function <code>leaves</code>", but there's some non-trivial mapping needed to go from sytnax of path to the relevant container</li>
<li>threading the side-table through all lowerings might be a pain. We should use the same table for all function arguments, etc. And if we split some of those into separate queries, we'll have to somehow unify the tables</li>
<li>there will be a ton of different side-tables for seemingly random bits of info an IDE might need. (This one actally is solved by a <a href="https://github.com/rust-analyzer/rust-analyzer/blob/ee904594af174866cfa10474fd8fd3f23580b6af/crates/ra_hir_def/src/dyn_map.rs" target="_blank" title="https://github.com/rust-analyzer/rust-analyzer/blob/ee904594af174866cfa10474fd8fd3f23580b6af/crates/ra_hir_def/src/dyn_map.rs">dyn_map</a>, which I consider a great solution to this problem,  although the conceptual complexity is high)</li>
<li>I think we want to use syntax trees as keys in the map, and that will be a pain on many levels:<ul>
<li>if we use literal <code>SyntaxNode</code>s, we'll retain <strong>all</strong> syntax trees via Arcs</li>
<li>if we use <code>(File, TextRange)</code> of a node insted, we'll need significanlty more legwork to go from the actual SyntaxNode to key/value (one direction is easy, another is hard)</li>
<li>either of the above two approaches breaks incrementality</li>
<li>we can store something like (<code>parent_item_id</code>, <code>relative_range</code>), which helps with incremental, but makes mapping even more inderect and ...</li>
<li>... looks like it doesn't solve the more fundamental problem that we <strong>don't</strong> need those tables most of the time at all, they are a waste of space</li>
</ul>
</li>
</ul>
<p>One thing I've tried to do is to basically make a <em>function</em> which returns a (Data, Map&lt;SyntaxNode, Stuff&gt;), which can either be called directly, or via a query which returns only <code>Data</code>.  The funny thing with this approach is that we do compute everything twice.</p>



<a name="183060904"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183060904" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183060904">(Dec 10 2019 at 13:54)</a>:</h4>
<p><span class="user-mention" data-user-id="129457">@Florian Diebold</span> yeah, diagnostics feel similar</p>



<a name="183061150"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183061150" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183061150">(Dec 10 2019 at 13:57)</a>:</h4>
<p>And, in fact, in Kotlin they use the same binding trace thing for both:</p>
<ol>
<li><a href="https://github.com/JetBrains/kotlin/blob/344bc33096f0a6786cfde8a85297be45fc6b9239/compiler/frontend/src/org/jetbrains/kotlin/resolve/lazy/descriptors/LazyTypeParameterDescriptor.java#L60" target="_blank" title="https://github.com/JetBrains/kotlin/blob/344bc33096f0a6786cfde8a85297be45fc6b9239/compiler/frontend/src/org/jetbrains/kotlin/resolve/lazy/descriptors/LazyTypeParameterDescriptor.java#L60">https://github.com/JetBrains/kotlin/blob/344bc33096f0a6786cfde8a85297be45fc6b9239/compiler/frontend/src/org/jetbrains/kotlin/resolve/lazy/descriptors/LazyTypeParameterDescriptor.java#L60</a></li>
<li><a href="https://github.com/JetBrains/kotlin/blob/344bc33096f0a6786cfde8a85297be45fc6b9239/compiler/frontend/src/org/jetbrains/kotlin/resolve/lazy/descriptors/LazyTypeParameterDescriptor.java#L67" target="_blank" title="https://github.com/JetBrains/kotlin/blob/344bc33096f0a6786cfde8a85297be45fc6b9239/compiler/frontend/src/org/jetbrains/kotlin/resolve/lazy/descriptors/LazyTypeParameterDescriptor.java#L67">https://github.com/JetBrains/kotlin/blob/344bc33096f0a6786cfde8a85297be45fc6b9239/compiler/frontend/src/org/jetbrains/kotlin/resolve/lazy/descriptors/LazyTypeParameterDescriptor.java#L67</a></li>
</ol>
<p>1 records an association between syntax and Kotlin's HIR, 2 records an error</p>



<a name="183061160"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183061160" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183061160">(Dec 10 2019 at 13:58)</a>:</h4>
<p>I feel like we 'just' need IDs for type refs similar to <code>ExprId</code>s and a source mapping for them... yeah, it'll be more work to get from a source location to the actual data, but it's the same thing we're already doing</p>



<a name="183061297"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183061297" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183061297">(Dec 10 2019 at 13:59)</a>:</h4>
<p><span class="user-mention" data-user-id="129457">@Florian Diebold</span> I am not sure... Like, the rest of the compiler doesn't care about what bits a <code>TypeRef</code> consists of, it only cares what it lowers to, as a whole.</p>



<a name="183067646"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183067646" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183067646">(Dec 10 2019 at 15:04)</a>:</h4>
<p>So, I think our options are:</p>
<ul>
<li>make sure that everything has an ID and store side-tables with such IDs as query values in salsa</li>
<li>store tables with stable AST pointers in salsa</li>
<li>don't store anything extra in salsa, but, in raw query function, compute a table which stores  (unstable)<code>SyntaxNode</code>s</li>
</ul>
<p>I am somewhat leaning towards the latter option, because it avoids the need to store stuff which we don't really need anyway.</p>



<a name="183067724"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183067724" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183067724">(Dec 10 2019 at 15:05)</a>:</h4>
<p>Also, cc <span class="user-mention" data-user-id="116009">@nikomatsakis</span> , I feel this thread an interesting question for the overall RLS 2.0 architecture .</p>



<a name="183067859"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183067859" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183067859">(Dec 10 2019 at 15:06)</a>:</h4>
<p>we could probably do simple path-like pointers for this, like <code>root -&gt; first type param -&gt; second type param</code>, that would be incremental-friendly and not require any changes to the <code>TypeRef</code> structure itself?</p>



<a name="183067942"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183067942" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183067942">(Dec 10 2019 at 15:07)</a>:</h4>
<p>and as long as the AST-&gt;HIR lowering is trivial, it would even not require a source map, though probably that won't stay that way</p>



<a name="183067977"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183067977" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183067977">(Dec 10 2019 at 15:07)</a>:</h4>
<p><span class="user-mention" data-user-id="129457">@Florian Diebold</span> for ast-stable pointers? Yeah, that's an option, though I think <code>(parent_item_id, relative_range)</code> might be a more-general, less code option.</p>



<a name="183068051"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183068051" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183068051">(Dec 10 2019 at 15:08)</a>:</h4>
<p>ranges, even relative ones, aren't as stable though... but probably that's fine</p>



<a name="183068221"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183068221" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183068221">(Dec 10 2019 at 15:10)</a>:</h4>
<p>Hm, actually I am confused here: if you are talkig about type <strong>parameters</strong>, that's already somewhat handled since couple of days ago. If you are talking about type <strong>arguments</strong> (and that are arguments in the initial screenshot), then the concept of <code>root</code>  is slighly fuzzy. </p>
<p>Relative ranges should be ok -- you re-run lowering code anyway if the syntax node changes. A somewhat painful moment here is that just range is not enough, there could be macros, so you'll need something like <code>InFile&lt;TextRange&gt;</code>...</p>



<a name="183068242"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183068242" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183068242">(Dec 10 2019 at 15:10)</a>:</h4>
<p>yeah, I mean type arguments</p>



<a name="183068279"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183068279" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183068279">(Dec 10 2019 at 15:11)</a>:</h4>
<p>basically, to be able to address any part of a type ref like <code>Result&lt;Vec&lt;Block::Hash&gt;&gt;</code></p>



<a name="183068303"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183068303" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183068303">(Dec 10 2019 at 15:11)</a>:</h4>
<blockquote>
<p>you re-run lowering code anyway if the syntax node changes</p>
</blockquote>



<a name="183068335"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183068335" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183068335">(Dec 10 2019 at 15:11)</a>:</h4>
<p>you re-run AST-&gt;HIR lowering, not necessarily HIR-&gt;type</p>



<a name="183068441"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183068441" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183068441">(Dec 10 2019 at 15:12)</a>:</h4>
<p>If AST-&gt;HIR stays the same, it's probably the case that relative ranges are the same as well. You loose optimizations on typing whitesapce, but that doesn't seem important</p>



<a name="183069633"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183069633" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183069633">(Dec 10 2019 at 15:24)</a>:</h4>
<p>yeah, that's what I was thinking of, but you're right, it doesn't seem important</p>



<a name="183069863"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183069863" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183069863">(Dec 10 2019 at 15:26)</a>:</h4>
<p>unless people start having huge type references spanning multiple lines I guess <span aria-label="sweat smile" class="emoji emoji-1f605" role="img" title="sweat smile">:sweat_smile:</span></p>



<a name="183070080"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183070080" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183070080">(Dec 10 2019 at 15:29)</a>:</h4>
<blockquote>
<p>then the concept of root is slighly fuzzy.</p>
</blockquote>
<p>I think there should always be a clear root from the query that actually does the lowering -- i.e. if you're lowering the return type in a function signature, that's where your root is, etc.</p>



<a name="183071722"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183071722" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183071722">(Dec 10 2019 at 15:46)</a>:</h4>
<p>Aha, I understand now, that's basically our <code>AstIdMap</code>, but extended to the bodies of the items. So, the id is something like "the nth descendant of a specific type". That would work, but would require threading the relevant mapping of syntax nodes to positional ids everywhere. </p>
<p>I sort of feel the core question is "do we store such a map in salsa at all?". If we do, we should pick <em>any</em> id scheme and be done with it. If we don't we can use syntax nodes themselves, which seems like it'd reduce complexity by a large constant factor.</p>



<a name="183074103"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183074103" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183074103">(Dec 10 2019 at 16:10)</a>:</h4>
<p>I'm not sure I understand how it would work without storing the map</p>



<a name="183074201"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183074201" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183074201">(Dec 10 2019 at 16:11)</a>:</h4>
<p>Some of the newer hir source-maps work this way: <a href="https://github.com/rust-analyzer/rust-analyzer/blob/ee904594af174866cfa10474fd8fd3f23580b6af/crates/ra_hir_def/src/child_by_source.rs#L105-L124" target="_blank" title="https://github.com/rust-analyzer/rust-analyzer/blob/ee904594af174866cfa10474fd8fd3f23580b6af/crates/ra_hir_def/src/child_by_source.rs#L105-L124">https://github.com/rust-analyzer/rust-analyzer/blob/ee904594af174866cfa10474fd8fd3f23580b6af/crates/ra_hir_def/src/child_by_source.rs#L105-L124</a></p>



<a name="183074281"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183074281" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183074281">(Dec 10 2019 at 16:12)</a>:</h4>
<p>Like, we basically have the same two queries (<code>foo</code> and <code>foo_with_source_map</code>), but <code>foo_with_source_map</code> is <code>#[salsa::transparent]</code>, so it can return <code>SyntaxNode</code>s directly</p>



<a name="183074339"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183074339" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183074339">(Dec 10 2019 at 16:13)</a>:</h4>
<p>basically == the actual implementation at the moment goes via a couple of abstractions which are probably overly-complex for the task at hand...</p>



<a name="183105989"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183105989" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183105989">(Dec 10 2019 at 21:46)</a>:</h4>
<p>in this case, we have two steps, though (AST -&gt; HIR and HIR -&gt; resolved type). We can't have the second step use <code>SyntaxNode</code>s directly, right?</p>



<a name="183109860"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183109860" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183109860">(Dec 10 2019 at 22:33)</a>:</h4>
<p>Hrm, you are correct...</p>



<a name="183109961"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183109961" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183109961">(Dec 10 2019 at 22:34)</a>:</h4>
<p>this... actually reminds me of another thing was thinking about recently. Current unresolved TypeRef doesn’t seem too useful</p>



<a name="183110085"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183110085" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183110085">(Dec 10 2019 at 22:36)</a>:</h4>
<p>the lowering code in Ty spends a lot of effor on path resolution, which ideally belongs to the hir_def crate. I wonder if we can get rid of TypeRef altogether? I am not exactly sure that it helps with incrementality</p>



<a name="183111041"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183111041" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183111041">(Dec 10 2019 at 22:50)</a>:</h4>
<p>Even more generally: hir::Path is convenient, because it’s a value type. But, to implement side tables, we’ll have to change it from value-type to a type with identity (by assigning ids to segments, or by using ast::Path directly). </p>
<p>We want two exactly opposite things at the same time :-(</p>



<a name="183111087"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183111087" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183111087">(Dec 10 2019 at 22:51)</a>:</h4>
<p>doing name resolution directly on the AST feels a bit weird ;) but maybe that's fine. I think type inference will need a way to refer to specific user-written types anyway though, so I don't think it gets us around that</p>



<a name="183111217"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183111217" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183111217">(Dec 10 2019 at 22:52)</a>:</h4>
<p>I'm not convinced that we need to give paths etc. identities for that though</p>



<a name="183111374"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183111374" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183111374">(Dec 10 2019 at 22:54)</a>:</h4>
<p>I guess in a sense, giving them an ID gives them an identity by definition, what I mean is it can stay a value type anyway</p>



<a name="183112282"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183112282" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183112282">(Dec 10 2019 at 23:06)</a>:</h4>
<p>Yeah, in my terminology a path with id is not a value type. To be less ambitious, today we have a property that <code>foo::bar</code> is indistinguishable from any other <code>foo::bar</code>. This seems to be a theoretically useful property: with it, you guarantee that name resolution looks only at the essential information and cant’ make different choices depending on, say, position of path within the file. With ids, <code>foo#1::bar#2</code> is not Eq to <code>foo#3::bar#4</code>, and we should manually ensure that resolver doesn’t care about specific ids....</p>



<a name="183112466"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183112466" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183112466">(Dec 10 2019 at 23:09)</a>:</h4>
<p>Again, a sort of theoretical way out of the problem is to use positional ids: number all segments in increasing order and, when passing a sub path to some method, appropriately increment indexes in the return of this method.</p>



<a name="183143328"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183143328" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183143328">(Dec 11 2019 at 10:21)</a>:</h4>
<p>Interesting!</p>
<p>Thinking about this more, the most interesting problem seems to be how do we implement goto def for imports (<code>use std::collections::HashMap</code>). This is the place where we want to avoid storing auxiliary info, if possible: <code>CrateDefMap</code> is already a costly data structure. </p>
<p>It's also interesting that Kotlin's imports <em>optionally</em> carry syntax with them, and side-table is recorded only for imports which carry syntax: </p>
<ul>
<li><a href="https://github.com/JetBrains/kotlin/blob/e2010cb90d6b6f420fb6b0cfecc9d7bb3754d342/compiler/psi/src/org/jetbrains/kotlin/psi/KtImportInfo.kt" target="_blank" title="https://github.com/JetBrains/kotlin/blob/e2010cb90d6b6f420fb6b0cfecc9d7bb3754d342/compiler/psi/src/org/jetbrains/kotlin/psi/KtImportInfo.kt">https://github.com/JetBrains/kotlin/blob/e2010cb90d6b6f420fb6b0cfecc9d7bb3754d342/compiler/psi/src/org/jetbrains/kotlin/psi/KtImportInfo.kt</a></li>
<li><a href="https://github.com/JetBrains/kotlin/blob/e2010cb90d6b6f420fb6b0cfecc9d7bb3754d342/compiler/frontend/src/org/jetbrains/kotlin/resolve/QualifiedExpressionResolver.kt#L153" target="_blank" title="https://github.com/JetBrains/kotlin/blob/e2010cb90d6b6f420fb6b0cfecc9d7bb3754d342/compiler/frontend/src/org/jetbrains/kotlin/resolve/QualifiedExpressionResolver.kt#L153">https://github.com/JetBrains/kotlin/blob/e2010cb90d6b6f420fb6b0cfecc9d7bb3754d342/compiler/frontend/src/org/jetbrains/kotlin/resolve/QualifiedExpressionResolver.kt#L153</a> (<code>lastPart.expression</code> can be null)</li>
</ul>



<a name="183145995"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183145995" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183145995">(Dec 11 2019 at 10:59)</a>:</h4>
<blockquote>
<p>Again, a sort of theoretical way out of the problem is to use positional ids: number all segments in increasing order and, when passing a sub path to some method, appropriately increment indexes in the return of this method.</p>
</blockquote>
<p>that seems like a (theoretically ;) ) nice approach to me</p>



<a name="183180969"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183180969" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183180969">(Dec 11 2019 at 17:38)</a>:</h4>
<p>Note: this will require to add "size of sub tree" field to hir::Path and friends.</p>



<a name="183189005"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183189005" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183189005">(Dec 11 2019 at 19:01)</a>:</h4>
<p>can't we just calculate that on the fly?</p>



<a name="183196837"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183196837" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183196837">(Dec 11 2019 at 20:13)</a>:</h4>
<p>That will work in one direction, but not in the other. Finding nth node in the tree needs subtree sizes, or it’ll be linear (which maybe is ok?)</p>



<a name="183197521"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183197521" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183197521">(Dec 11 2019 at 20:20)</a>:</h4>
<p>I'm assuming it'd be ok since paths and typerefs aren't going to be very big</p>



<a name="183244272"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183244272" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Florian Diebold <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183244272">(Dec 12 2019 at 09:55)</a>:</h4>
<p>... and would we actually need to ever find the nth node? I think we just need to have the current ID while walking the whole thing, and find the ID from the node</p>



<a name="183244753"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183244753" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183244753">(Dec 12 2019 at 10:02)</a>:</h4>
<p>Maybe i am thinking about somehting different?</p>
<p>Consider something like <code>VariantData</code>, which stores a type ref for each field. I <em>think</em> we want to have "ids" of segments of paths in <em>different</em> fields be different, because we lower at variant granularity (ids might be the same between different structs though).</p>
<p>In this setup, when we zoom into a specific field, we need to know the largest ID int he preceeding fields</p>



<a name="183245561"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183245561" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183245561">(Dec 12 2019 at 10:13)</a>:</h4>
<p>TBH, I can't imagine in full details how the scheme would work. I wonder if we should start trying things out? So far, I see these three alternatives (one of which isn't)</p>
<ul>
<li>get rid of <code>TypeRef</code> and try to lower ast to types directly (this won't work, because <code>TypeRef</code>s are stored in <code>Body</code> (for casts, for example), and we absolutely can't get rid of body lowering step)</li>
<li>Add a numeric ID to each path segment, local to each item. and maintain a <code>Map&lt;SegID, ast::Path&gt;</code> and <code>Map&lt;SegID, Resolution&gt;</code> maps</li>
<li>Don't  add a <em>explicit</em> numeric ID to each path, but still construct maps exactly as a above, by relying on implicit positional IDs.</li>
</ul>
<p>That is, the actual IDs should be exactly the same in both cases, the question is how do we store them.<br>
Note that the last two approaches probably wont' work for paths in modules (for uses and top-level macros), because that would make crate def map more brittle and large. But I think it's ok to use re-derive approach for module paths, expecially if we separate "paths with ::&lt;&gt;" for use-style paths</p>



<a name="183646677"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183646677" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183646677">(Dec 17 2019 at 13:15)</a>:</h4>
<p>Found an interesting case here. Currently the <code>hir::Path</code> doesn't handle nested supers, like <code>super::super::super</code>. A <em>natural</em> way to model that is</p>
<div class="codehilite"><pre><span></span>enum PathAnchor {
  Super(u8), // Super(0) == self::
}
</pre></div>


<p>That is, we lower a sequence of identifiers to a number... This seems like a case where implicit numbering of segments would be the most convenient</p>



<a name="183658832"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183658832" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183658832">(Dec 17 2019 at 15:30)</a>:</h4>
<p><span class="user-mention" data-user-id="133169">@matklad</span> (I'm catching up here -- I've been feeling quite guilty about dropping salsa development on the floor, but I definitely had thoughts about "side channels" for diagnostics, I forget if we ever discussed them, I guess they might plausibly apply here too)</p>



<a name="183658881"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183658881" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183658881">(Dec 17 2019 at 15:31)</a>:</h4>
<p>I'll try finish reading but maybe we could also have some sync time for a deeper discussion</p>



<a name="183691328"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/183691328" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#183691328">(Dec 17 2019 at 21:03)</a>:</h4>
<p><span class="user-mention" data-user-id="116009">@nikomatsakis</span> sync time would be valuable, I think! So far, we have two questions:</p>
<ul>
<li>the one in this thread</li>
<li>the one about eager macros</li>
</ul>
<p>And there's also the borrowed key work, which I anticipate a lot :)</p>



<a name="189523082"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/189523082" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#189523082">(Mar 02 2020 at 18:54)</a>:</h4>
<p>Opened <a href="https://github.com/rust-analyzer/rust-analyzer/issues/3407" target="_blank" title="https://github.com/rust-analyzer/rust-analyzer/issues/3407">https://github.com/rust-analyzer/rust-analyzer/issues/3407</a> to not forget about this.</p>



<a name="189523350"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/189523350" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#189523350">(Mar 02 2020 at 18:56)</a>:</h4>
<p>With side tables it might be possible to store them on disk. Maybe that would be easier than implementing persistence in salsa?</p>



<a name="189523408"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/189523408" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#189523408">(Mar 02 2020 at 18:57)</a>:</h4>
<p>CC <a href="https://github.com/salsa-rs/salsa/issues/10" target="_blank" title="https://github.com/salsa-rs/salsa/issues/10">https://github.com/salsa-rs/salsa/issues/10</a>, of course</p>



<a name="189523484"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/189523484" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#189523484">(Mar 02 2020 at 18:57)</a>:</h4>
<p>I think these are mostly orthogonal issues.</p>



<a name="189523555"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/189523555" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#189523555">(Mar 02 2020 at 18:58)</a>:</h4>
<p>I also wonder if we can somehow apply the tree identity trick of <code>hir::Semantics</code> here...</p>



<a name="189524391"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/189524391" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> std::Veetaha <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#189524391">(Mar 02 2020 at 19:06)</a>:</h4>
<p>In one of your posts you said that being lazy and not storing hash-tables is what makes and IDE vs compiler. What changed?</p>



<a name="189524711"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/189524711" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#189524711">(Mar 02 2020 at 19:09)</a>:</h4>
<blockquote>
<p>not storing hash-tables</p>
</blockquote>
<p>Not storing hash tables where you can use an array</p>



<a name="189524836"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/189524836" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#189524836">(Mar 02 2020 at 19:10)</a>:</h4>
<blockquote>
<p>In one of your posts you said that being lazy and not storing hash-tables is what makes and IDE vs compiler. What changed?</p>
</blockquote>
<p>I must say I don't really understand this question, as i don't see any kind of contradiction between this discussion and sorbet discussion</p>



<a name="189526895"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Architecture%20quetion%3A%20to%20remember%20or%20to%20compute/near/189526895" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> std::Veetaha <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Architecture.20quetion.3A.20to.20remember.20or.20to.20compute.html#189526895">(Mar 02 2020 at 19:29)</a>:</h4>
<p>Sorry, I might've missed the point, I was referring to <a href="https://rust-analyzer.github.io/blog/2019/11/13/find-usages.html#compilers-approach" target="_blank" title="https://rust-analyzer.github.io/blog/2019/11/13/find-usages.html#compilers-approach">this post</a></p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>